Ch.18 Applications

Stochastic Matrices

A matrix is stochastic if all entries are nonnegative and the sum of the entries of each column are $1$ .
If every entry is positive the matrix is said to be positive
These are common in probabilistic phenomena (Markov chains)

Suppose a movie can be rented from location 1, 2, or 3 and returned to any location. Let $A$ be matrix whose $ij$ entry is the probability a customer renting a movie from location $j$ returns it to location $i$
$A=\begin{pmatrix}.3&.4&.5\\.3&.4&.3\\.4&.2&.2\end{pmatrix}$
The columns sum to 1 because a movie rented has a $100\%$ chance of getting returned to some location.

Now, let $v=(x,y,z)$ represent the number of movies at the three locations. Then there will be approximately
$Av=A\begin{pmatrix}x\\y\\z\end{pmatrix}=\begin{pmatrix}.3x+.4y+.5z\\.3x+.4y+.3z\\.4x+.2y+.2z\end{pmatrix}$
movies in the three locations the next day. Since the columns add to 1, the total number won't change.

If $x_n,y_n,z_n$ are the number of movies in location $1,2,3,$ on day $n$ , then
$v_n=Av_{n-1}=A^2v_{n-2}=\cdots=A^nv_0$

An iteration $v_{n+1}=Av_n$ is used to model a state change controlled by a matrix:

$v_n$ is the state at time $n$
$v_{n+1}$ is the state at time $n+1$
$A$ is the change of state matrix

Eigenvalues

To compute $A^nv_0$ , it can help to use eigenvalues.
A stochastic matrix always has an eigenvalue of $1$ .

Proof

Consider $3\times3$ stochastic matrix
$A=\begin{pmatrix}x_1&y_1&z_1\\x_2&y_2&3_2\\x_3&y_3&z_3\end{pmatrix}$
Since the columns add to $1$ , the rows of $A^T$ add to $1$ . Thus, $(1,1,1)$ is an eigenvector with eigenvalue $1$ .
$\begin{pmatrix}x_1&x_2&x_3\\y_1&y_2&y_3\\z_1&z_2&z_3\end{pmatrix}\begin{pmatrix}1\\1\\1\end{pmatrix}=\begin{pmatrix}x_1+x_2+x_3\\y_1+y_2+y_3\\z_1+z_2+z_3\end{pmatrix}=1\cdot\begin{pmatrix}1\\1\\1\end{pmatrix}$

Any other eigenvalue is less than $1$ . That is, $1$ is the largest eigenvalue of a stochastic matrix.

Proof

Let $v=\begin{pmatrix}x_1\\x_2\\\vdots\\x_n\end{pmatrix}$ be an eigenvalue of positive stochastic matrix $A$ .
$\lambda v=A^Tv\implies \lambda x_j=\sum_{i=1}^na_{ij}x_i$
Choose $x_j$ with the largest absolute value, so that $|x_i|\le|x_j$ for all $i$ . Then
$|\lambda|\cdot|x_j|=\left|\sum_{i=1}^na_{ij}x_i\right|\le\sum_{i=1}^na_{ij}|x_i|\le\sum_{i=1}^na_{ij}|x_j|=1\cdot|x_j|$
The first inequality is valid since $A$ is a positive matrix. The final equality holds since $A$ is stochastic.

Let $A=\begin{pmatrix}3/4&1/4\\1/4&3/4\end{pmatrix}$ . $A$ is diagonalizable, with $A=PDP^{-1}$ where
$\begin{array}{cc}P=\begin{pmatrix}1&1\\1&-1\end{pmatrix}&D=\begin{pmatrix}1&0\\0&1/2\end{pmatrix}\end{array}$

Diagonalization Process

The characteristic polynomial is $(3/4-\lambda)^2-(1/4)^2$ , so the eigenvalues are $1$ and $1/2$ .
Thus, $D=\begin{pmatrix}1&0\\0&1/2\end{pmatrix}$
An eigenvector with associated eigenvalue $1$ is $\begin{pmatrix}1\\1\end{pmatrix}$ , as seen before.
An eigenvector with associated eigenvalue $1/2$ can be found by solving $(A-1/2I)v=0$
$\begin{pmatrix}1/4&1/4\\1/4&1/4\end{pmatrix}\begin{pmatrix}x\\y\end{pmatrix}=0$
gives the solution set $\{\begin{pmatrix}1\\-1\end{pmatrix}t\space|\space t\in\mathbb{R}\}$
So, we have $P=\begin{pmatrix}1&1\\1&-1\end{pmatrix}$

$A^n$ acts on usual coordinates in the same way $D$ acts on $B=\langle w_1=\begin{pmatrix}1\\1\end{pmatrix},w_2=\begin{pmatrix}1\\-1\end{pmatrix}\rangle$ , so $\text{Rep}_B(A^nx)=D^n\text{Rep}_B(x)$ . Thus,
$\text{Rep}_B(x)=\begin{pmatrix}c_1\\c_2\end{pmatrix}\implies \text{Rep}_B(A^nx)=\begin{pmatrix}1&0\\0&1/2^n\end{pmatrix}\begin{pmatrix}c_1\\c_2\end{pmatrix}=\begin{pmatrix}c_1\\c_2/2^n\end{pmatrix}$
Thus, $A^nx=c_1w_1+c_2/2^nw_2$ . As $n$ grows larger, the second term approaches $0$ , so $A^nx$ approaches $c_1w_1$ , an eigenvector with eigenvalue $1$ . So, all vectors get "sucked into" the $1$ -eigenspace spanned by $\begin{pmatrix}1\\1\end{pmatrix}$

This means that after a sufficiently large iterations $v_{n+1}=Av_n$ , the state does not change; i.e. $Av=v$ . That vector $v$ in which the state stabilizes is in the $1$ -eigenspace of $A$ .

A steady state for stochastic matrix $A$ is an eigenvector $w$ with eigenvalue $1$ such that all entries are positive and add to $1$ .

Perron-Frobenius Theorem

If $A$ is a positive stochastic matrix, then it has a unique steady state vector $w$ spanning the $1$ -eigenspace. Moreover, for any $v_0$ with entries summing to $c$ , $Av_n=Av_{n-1}v$ approaches $cw$ .
In other words:

the $1$ -eigenspace of a positive stochastic matrix is a line
taking any $1$ -eigenvector and dividing by the sum of the entries always results in a steady state with positive entries that sum to $1$
$w$ is like steady state percentages; the same percentage will be there the next day
the sum $c$ is the total number; eventually, they arrange themselves according to the steady state percentage $cw$

Google PageRank

importance rule: if page $P$ links to $n$ other pages $Q_1,...,Q_n$ , then each $Q_i$ inherits $1/n$ of $P$ 's importance

Consieder this $4$ -page network

We can compute an importance matrix

Each color corresponds to that page giving its inheritance to the pages it links to
By the importance rule, we can set the equation
$\begin{pmatrix}c+\frac{1}{2}d\\\frac{1}{3}a\\\frac{1}{3}a+\frac{1}{2}b+\frac{1}{2}d\\\frac{1}{3}a+\frac{1}{2}b\end{pmatrix}=\begin{pmatrix}a\\b\\c\\d\end{pmatrix}$

We see that the importance matrix is a positive stochastic matrix and the rank vector is an eigenvector with eigenvalue $1$ . This is a steady state.

If a page links to no other page, its column will sum to 0, making the resulting matrix not stochastic.

Additionally, if there are two distinct "islands" of pages, there may be more than one eigenvector with eigenvalue $1$ .

To solve this, fix $p\in(0,1)$ , the dampening factor (typically $p=0.15$ ). The Google Matrix is
$M=(1-p)+p\cdot B\text{ where }B=\frac{1}{N}\begin{pmatrix}1&1&\cdots&1\\1&1&\cdots&1\\\vdots&\vdots&\ddots&\vdots\\1&1&\cdots&1\end{pmatrix},$
$N$ is the total number of pages, and $A$ is the importance matrix.

This is a stochastic matrix, and solves both of the problems above.